from typing import *


class Solution:
    def maxTargetNodes(
        self, edges1: List[List[int]], edges2: List[List[int]], k: int
    ) -> List[int]:

        def f(edge, d):
            n = len(edge) + 1
            next = [[] for _ in range(n)]
            for a, b in edge:
                next[a].append(b)
                next[b].append(a)

            def g(parent, node, height, d):
                if height > d:
                    return 0
                ans = 1
                for nxt in next[node]:
                    if nxt != parent:
                        ans += g(node, nxt, height + 1, d)
                return ans

            dp = [0] * n
            for i in range(n):
                dp[i] = g(None, i, 0, d)
            return dp

        d1 = f(edges1, k)
        d2 = f(edges2, k - 1)
        mx = max(d2)
        n = len(edges1) + 1
        ans = [0] * n
        for i in range(n):
            ans[i] = d1[i] + mx
        return ans


s = Solution()
print(
    s.maxTargetNodes(
        edges1=[[0, 1], [0, 2], [2, 3], [2, 4]],
        edges2=[[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]],
        k=2,
    )
)
